// 2025/3/4
// https://leetcode.cn/problems/maximum-subarray/?envType=study-plan-v2&envId=top-100-liked
// 最大子数组和

// 动态规划(反思，居然没想到)
class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int n = nums.size();
            int pre = 0, ans = -10e4 - 1;
            for(int i = 0; i < n; i++)
            {
                pre = max(pre + nums[i], nums[i]);
                ans = max(ans, pre);
            }
            return ans;
        }
    };

// 分治
class Solution {
    public:
        struct Status{
            int lSum, rSum, mSum, iSum;
        };
    
        Status pushUp(Status lSub, Status rSub)
        {
            int lSum = max(lSub.lSum, lSub.iSum + rSub.lSum);
            int rSum = max(rSub.rSum, rSub.iSum + lSub.rSum);
            int mSum = max(lSub.rSum + rSub.lSum, max(lSub.mSum, rSub.mSum));
            int iSum = lSub.iSum + rSub.iSum;
            return (Status){lSum, rSum, mSum, iSum};
        }
    
        Status get(vector<int>& nums, int l, int r)
        {
            if(l == r)
                return (Status){nums[l], nums[l], nums[l], nums[l]};
    
            int m = (l + r) >> 1;
            Status lSub = get(nums, l, m);
            Status rSub = get(nums, m + 1, r);
            return pushUp(lSub, rSub);
        }
    
        int maxSubArray(vector<int>& nums) {
            return get(nums, 0, nums.size() - 1).mSum;
        }
    };